package problem994;

import java.util.LinkedList;
import java.util.Queue;

//994.腐烂的橘子
//https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int orangesRotting(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] st = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        int ret = 0;
        int[] xx = {1, -1, 0, 0};
        int[] yy = {0, 0, 1, -1};
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] t = queue.poll();
                for(int i = 0; i<4; i++) {
                    int dx = t[0] + xx[i];
                    int dy = t[1] + yy[i];
                    if(dx >= 0 && dx < n && dy >= 0 && dy < m && grid[dx][dy] == 1 && !st[dx][dy]) {
                        st[dx][dy] = true;
                        queue.add(new int[]{dx, dy});
                    }
                }
            }
            ret ++;
        }

        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1 && !st[i][j]) {
                    return -1;
                }
            }
        }
        return ret-1 > 0 ? ret-1 : 0;
    }
}